package BST

import "fmt"

type node struct {
	value  int
	left   *node
	right  *node
	parent *node
}

func createBST(data []int) *node {
	var tree *node
	for _, x := range data {
		tree = insertNode(x, tree)
	}
	return tree
}

func insertNode(x int, tree *node) *node {
	if tree == nil {
		tree = newNode(x, nil, nil, tree)
		return tree
	}
	if tree.value > x {
		if tree.left == nil {
			tree.left = newNode(x, nil, nil, tree)
			return tree
		}
		insertNode(x, tree.left)
		return tree
	}
	if tree.value < x {
		if tree.right == nil {
			tree.right = newNode(x, nil, nil, tree)
			return tree
		}
		insertNode(x, tree.right)
	}
	return tree
}

func newNode(v int, left *node, right *node, parent *node) *node {
	return &node{
		value:  v,
		left:   left,
		right:  right,
		parent: parent,
	}
}

func inOrderWalk(tree *node) {
	if tree == nil {
		return
	}
	inOrderWalk(tree.left)
	fmt.Println(tree.value)
	inOrderWalk(tree.right)
}

func preOrderWalk(tree *node) {
	if tree == nil {
		return
	}
	fmt.Println(tree.value)
	preOrderWalk(tree.left)
	preOrderWalk(tree.right)
}

func postOrderWalk(tree *node) {
	if tree == nil {
		return
	}
	postOrderWalk(tree.left)
	postOrderWalk(tree.right)
	fmt.Println(tree.value)

}

func bstSearch(x int, tree *node) *node {
	if tree == nil {
		return nil
	}
	if tree.value == x {
		return tree
	}
	if x < tree.value {
		return bstSearch(x, tree.left)
	}
	if x > tree.value {
		return bstSearch(x, tree.right)
	}
	return nil

}
func bstSearchV2(x int, tree *node) *node {
	for tree != nil && tree.value != x {
		if x < tree.value {
			tree = tree.left
		} else {
			tree = tree.right
		}
	}
	return tree
}

func bstpred(tree *node) *node {
	if tree.left != nil {
		return maxNode(tree.left)
	}
	if tree.parent == nil {
		return nil
	}
	if tree.parent.right == tree {
		return tree.parent
	}
	if tree.parent.left == tree {
		p := tree
		for p.parent.left == p {
			p = p.parent
		}
		if p.parent.right == p {
			return p.parent
		}
	}
	return nil
}

func maxNode(tree *node) *node {
	if tree == nil {
		return nil
	}
	maxLeft := maxNode(tree.left)
	maxRight := maxNode(tree.right)
	node := tree
	if maxLeft != nil && maxLeft.value > node.value {
		node = maxLeft
	}
	if maxRight != nil && maxRight.value > node.value {
		node = maxRight
	}
	return node
}
